/*
 * @Author: dadadaXU 1413107032@qq.com
 * @Date: 2025-02-15 16:51:36
 * @LastEditors: dadadaXU 1413107032@qq.com
 * @LastEditTime: 2025-02-18 11:59:08
 * @FilePath: \LeetCode\1143.最长公共子序列.cpp
 * @Description: 这是默认设置,请设置`customMade`, 打开koroFileHeader查看配置 进行设置: https://github.com/OBKoro1/koro1FileHeader/wiki/%E9%85%8D%E7%BD%AE
 */
/*
 * @lc app=leetcode.cn id=1143 lang=cpp
 *
 * [1143] 最长公共子序列
 *
 * 方法1：分治算法 - 自顶向下划分子问题
 * - 存在的问题：子问题被重复求解 -> 两者情况划分后的子问题
 X = X1, X2,..., Xn
 Y = Y1, Y2,..., Ym
 * - 如果 Xn == Ym
 *   LCS(X[1...n], Y[1...m]) = LCS(X[1...n-1], Y[1...m-1]) + 1
 * - 如果 Xn != Ym
 *   LCS(X[1...n], Y[1...m]) = max{LCS(X[1...n-1], Y[1...m]), LCS(X[1...n], Y[1...m-1])}
 *
 * 方法2：动态规划 - 改进方法1
 * - 存储状态 dp[x][y]
 *
 * 方法3：动态规划 - 非递归
 * - 自底向上得到 dp[n][m]
 */
#include <string>
#include <vector>
#include <iostream>

// @lc code=start
class Solution
{
public:
    int LCS01(const std::string &text1, size_t len1, const std::string &text2, size_t len2)
    {
        if (len1 <= 0 || len2 <= 0)
            return 0;

        if (text1[len1 - 1] == text2[len2 - 1])
            return LCS01(text1, len1 - 1, text2, len2 - 1) + 1;
        else
            return std::max(LCS01(text1, len1 - 1, text2, len2),
                            LCS01(text1, len1, text2, len2 - 1));
    }

    std::vector<std::vector<int>> dp_LCS;

    /* dp_LCS 初始化为 -1 */
    int LCS02(const std::string &text1, int x, const std::string &text2, int y)
    {
        if (x < 0 || y < 0)
            return 0;

        if (dp_LCS[x][y] >= 0)
            return dp_LCS[x][y];

        if (text1[x] == text2[y])
            dp_LCS[x][y] = LCS02(text1, x - 1, text2, y - 1) + 1;
        else
            dp_LCS[x][y] = std::max(LCS02(text1, x - 1, text2, y),
                                    LCS02(text1, x, text2, y - 1));
        return dp_LCS[x][y];
    }

    int longestCommonSubsequence(std::string text1, std::string text2)
    {
        const int len1 = text1.length();
        const int len2 = text2.length();

        dp_LCS.resize(len1 + 1, std::vector<int>(len2 + 1, 0)); // 初始化为 0

        for (int x = 1; x <= len1; x++)
        {
            for (int y = 1; y <= len2; y++)
            {
                /* LCS(X[1...n], Y[1...m]) = LCS(X[1...n-1], Y[1...m-1]) + 1 */
                if (text1[x - 1] == text2[y - 1])
                    dp_LCS[x][y] = dp_LCS[x - 1][y - 1] + 1;
                /* LCS(X[1...n], Y[1...m]) = max{LCS(X[1...n-1], Y[1...m]), LCS(X[1...n], Y[1...m-1])} */
                else
                    dp_LCS[x][y] = std::max(dp_LCS[x - 1][y], dp_LCS[x][y - 1]);
            }
        }

        return dp_LCS[len1][len2];
    }
};
// @lc code=end

int main(void)
{
    Solution solution;
    std::cout << solution.longestCommonSubsequence("abcde", "def") << std::endl;
    return 0;
}